package com.warningrc.demo;

import java.util.ArrayList;
import java.util.Stack;


public class DFS_3 {
    // 定义图节点类
    static class Node {
        // 节点的值
        int value;
        // 存储该节点的邻接节点列表
        ArrayList<Node> neighbors;

        Node(int value) {
            this.value = value;
            this.neighbors = new ArrayList<>();
        }
    }
    // 判断有向图强连通分量的方法，接受起始节点作为参数
    public static ArrayList<ArrayList<Integer>> findStronglyConnectedComponents(Node start) {
        ArrayList<ArrayList<Integer>> components = new ArrayList<>();
        boolean[] visited = new boolean[100]; // 假设图中最多有100个节点，根据实际情况调整大小
        // 对原始图进行DFS遍历，标记可达节点
        dfs(start, visited);
        // 构建反向图
        Node[] reverseGraph = buildReverseGraph(start);
        // 重置访问标记数组
        visited = new boolean[100];
        // 遍历所有节点
        for (int i = 0; i < reverseGraph.length; i++) {
            if (reverseGraph[i]!= null &&!visited[i]) {
                ArrayList<Integer> component = new ArrayList<>();
                // 对反向图进行DFS遍历，找到强连通分量
                findSCCUtil(reverseGraph[i], visited, component);
                components.add(component);
            }
        }
        return components;
    }

    // 辅助的深度优先搜索方法，用于标记从给定节点可达的所有节点（用于原始图遍历）
    private static void dfs(Node node, boolean[] visited) {
        Stack<Node> stack = new Stack<>();
        stack.push(node);
        visited[node.value] = true;
        while (!stack.isEmpty()) {
            Node current = stack.pop();
            for (Node neighbor : current.neighbors) {
                if (!visited[neighbor.value]) {
                    stack.push(neighbor);
                    visited[neighbor.value] = true;
                }
            }
        }
    }

    // 构建原始图的反向图
    private static Node[] buildReverseGraph(Node start) {
        ArrayList<Node> nodes = new ArrayList<>();
        findAllNodes(start, nodes);
        Node[] reverseGraph = new Node[100]; // 假设图中最多有100个节点，根据实际情况调整大小
        for (Node node : nodes) {
            reverseGraph[node.value] = new Node(node.value);
        }
        for (Node node : nodes) {
            for (Node neighbor : node.neighbors) {
                reverseGraph[neighbor.value].neighbors.add(node);
            }
        }
        return reverseGraph;
    }

    // 辅助方法，用于找到图中的所有节点（通过递归遍历邻接节点）
    private static void findAllNodes(Node node, ArrayList<Node> nodes) {
        if (!nodes.contains(node)) {
            nodes.add(node);
            for (Node neighbor : node.neighbors) {
                findAllNodes(neighbor, nodes);
            }
        }
    }

    // 辅助的深度优先搜索方法，用于找到强连通分量（用于反向图遍历）
    private static void findSCCUtil(Node node, boolean[] visited, ArrayList<Integer> component) {
        Stack<Node> stack = new Stack<>();
        stack.push(node);
        visited[node.value] = true;
        component.add(node.value);
        while (!stack.isEmpty()) {
            Node current = stack.pop();
            for (Node neighbor : current.neighbors) {
                if (!visited[neighbor.value]) {
                    stack.push(neighbor);
                    visited[neighbor.value] = true;
                    component.add(neighbor.value);
                }
            }
        }
    }
}